Multi-tone transmission based communication systems such as Digital Subscriber Line (DSL) systems are widely used as a last-mile solution to provide broadband access to end users. In these systems, data is transmitted through the copper pairs traditionally used only for telephony. By using the existing infrastructure to provide broadband access, DSL systems are an attractive and cost-effective solution to last-mile access. Examples of DSL technologies (sometimes called xDSL) include High Data Rate Digital Subscriber Line (HDSL), Asymmetric Digital Subscriber Line (ADSL), and Very-high-bit-rate Digital Subscriber Line (VDSL).
A standard DSL line consists of a twisted wire copper-pair, which are deployed together in a cable, called binder. This binder typically origins from a Central Office (CO) and is split off into smaller portions towards the opposite end. The proximity of the pairs results in electromagnetic coupling, so that signals from one line interfere with the others. This impairment is known as crosstalk, and is one of the main factors limiting the achievable data rates in DSL systems. However, the popularity of services like video streams, which require high bit rates, is constantly driving the service providers to offer increased data rates. To provide these rates, methods that deal with crosstalk are needed.
One powerful crosstalk mitigating technique for downstream transmission is known as pre-processing or pre-coding. In the downstream, the signals in most of the pairs in a binder originate from the same central office (CO). Thus, a pre-processor, also referred to as pre-coder, may jointly process the signals from the corresponding lines prior to transmission in the CO. One simple and effective pre-processor employs linear processing. In this case, the signal transmitted in a given line after the pre-processor is actually a linear combination of the signals from all the lines. By choosing an appropriate linear combination, i.e. an appropriate pre-processor, the crosstalk can be greatly reduced.
Another important aspect of high-performance DMT-based DSL systems is bit-loading, i.e. determining how many bits each line should transmit in each tone. The challenge here is to maximize the number of bits while observing several, usually conflicting, constraints. On the one hand, a certain performance requirement, often expressed in terms of bit error rate (BER), i.e. a target BER, must be guaranteed. If the bit rate is increased, a higher transmit power is required in order to fulfil the target BER. On the other hand, the power that can be used in each copper pair is limited by practical considerations, such as the limited dynamic range of the power amplifiers and the impact of the signal on other lines or services as well as restrictions due to legislation. A good bit allocation algorithm is crucial for achieving high bit rates under the power constraints imposed by the system.
A pre-processed DSL system with a per-line power constraint is shown in FIG. 1. FIG. 1 shows a source coupled to a Central Office (CO). The CO is typically the connection point between an underlying network and a network connected user. It hosts a multiple of CO-modems concentrated in DSLAMs (DSL-Access-Multiplexer). CO-modems are connected to user-modems, often referred to as Customer-Premises-Equipment (CPE). In conventional systems, each DSL connection (line) defined by one CO-modem, a CPE and a connecting line between both, is driven independently of each other.
The CO is only provided as one example. It is also possible is to use so-called cabinets, which is a remote unit in the field hosting a multiple of DSLAMs to for instance reduce the distance between the CO-modem and the CPE, i.e. the line length, and is fed by a CO Both, CO and cabinet build practically a convergence entity for a multitude of DSL-connections.
As with all DMT-based systems, the transmission is divided into several tones, which do not interfere with one another. I.e. one tone uses a predetermined frequency range. With further reference to FIG. 1, the CO comprises for each tone one modulator per line. Before generating the actual channel input the connections that usually are driven independently, but affecting each other, may be processed in a coordinated manner, referred to as pre-processing in order to reduce crosstalk which is described above. The modulated information signal from the l-th line at the k-th tone, {tilde over (x)}lk, goes through the pre-processor Pk before generating the actual channel input at the k-th tone in the l-th line of the binder, xlk.
A per-line power constraint is illustrated in FIG. 1, where it can be seen that the sum of the powers of all the signals transmitted in the different tones of the same line must be less than a predetermined maximal power Pmax. In this specification it is assumed that the information signals from different users are uncorrelated.
As stated above, one of the main features of DSL systems is the use of DMT modulation, which essentially divides the channel seen by a user into several parallel channels, called subchannel or tones, and which are modelled as additive-white Gaussian noise (AWGN) channels. The k-th tone of the l-th line is then characterized by its complex gain, hk,l, and its noise variance, σk,l2. The problem of bit allocation, also referred to as bit-loading, is then to determine how many bits each line should transmit in each tone while ensuring that the system conforms to the given per-line power constraints and at the same time fulfils given requirements like maximum bit error rate. A major difficulty is that, due to the pre-coding, the power transmitted on a given line actually depends on the power allocated to all the lines. In other words, allocating a bit to a given line at a given tone actually increases the power transmitted on all lines at that particular tone.
Several bit allocation algorithms have been proposed in the literature. Most of them are based on the gap approximation, as disclosed in G. D. Forney and G. Ungerboeck, “Modulation and coding for linear Gaussian channels,” IEEE Trans. Inform. Theory, vol. 44, pp. 2384-2415, October 1998. The gap approximation stems from the following observation. Consider the signal-to-noise ratio (SNR) needed to transmit an M-QAM constellation with a given BER on an additive-white Gaussian noise (AWGN) channel. Also consider the minimum SNR required, according to established Information Theory, to transmit log2(M) bits on the same AWGN channel. The observation leading to the gap approximation is that the difference between these two values in dB, simply called the gap Γ, is constant, regardless of M. Using the gap approximation, it is possible to write the number of bits that can be transmitted on an AWGN channel using a QAM constellation as
                    b        =                                            log              2                        ⁡                          (                              1                +                                                      S                    ⁢                                                                                  ⁢                    N                    ⁢                                                                                  ⁢                    R                                    Γ                                            )                                .                                    (        1        )            
The equation (1) makes it possible to determine the energy needed to transmit a certain number of bits with a given BER. Further, let the SNR of a given channel be given bySNR=εk,lρk,l,  (1)where εk,l is the transmitted energy on tone k and line l, and ρk,l is defined as
      ρ          k      ,      l        =                                                    h                          k              ,              l                                                2                    σ                  k          ,          l                2              .  
Then, if it is desired to transmit bk,l bits in the k-th tone of the l-th line with a given BER, the necessary energy is given by
                              ɛ                      k            ,            l                          =                                            Γ                              ρ                                  k                  ,                  l                                                      ⁡                          [                                                2                                      b                                          k                      ,                      l                                                                      -                1                            ]                                .                                    (        3        )            
Note that using an error-correcting coding scheme typically decreases the gap. The amount of reduction depends on the particular code used. An ideal code would decrease the gap to 0 dB, so that the number of bits in this case would coincide with the maximum theoretical rate given by information theory. On the other hand, it may be desirable to increase the gap to introduce some safety margin, thus increasing the system robustness against non-stationary noise.
Most of the existing bit-loading algorithms are only applicable to a single-user system, for which the well-known Campello's algorithm e.g. described in J. Campello, “Practical Bit Loading for DMT” Proc. IEEE International Conference on Communications, pp. 801-805, June 1999, provides an optimal bit allocation. Campello's algorithm is based on the idea of incremental allocation. Initially, zero bits are allocated to each tone. Then, at each iteration, the algorithm uses equation (3) to compute the incremental energy needed to transmit one more bit on the k-th tone. This incremental energy is defined as the difference between the energy currently allocated to the k-th tone and the energy that would need to be allocated to this tone if it were to transmit one more bit. The algorithm then allocates the bit to the tone requiring the least incremental energy. The iterations then repeat, with the algorithm allocating bits one at a time until a power constraint is violated.
It should be noted that Campello's algorithm ignores the presence of other lines, and the resulting crosstalk is just considered as ordinary background noise. In a multi-user DSL environment bit allocation becomes more involved, since in this case both background noise and crosstalk adversely affect the received signal. Assuming that no crosstalk mitigating algorithms are used, the SNR in equation (1) must be replaced by a signal-to-interference-plus-noise ratio (SINR), since in this case crosstalk is also treated as noise.
Obviously, the SINR of a given line depends on the power of the remaining lines. Thus, if a bit is allocated to a given line, the power in the corresponding line must be increased, which decreases the SINR on the other lines. If this decrease is not compensated for, the BER on the other lines will increase. In other words, the problem of bit allocation in the multi-user case is coupled between the lines, because the bits cannot be allocated to a line with no consideration to the others. In this case the optimum solution is unknown, and sub-optimal algorithms have been proposed in the literature.
One such algorithm, based on Campello's algorithm, is presented by Lee, Sonalkar and Cioffi in L. Lee, R. V. Sonalkar and J. M. Cioffi, “Multi-user discrete bitloading for DMT-based DSL systems” in Proc. IEEE Global Telecommunications Conference, vol. 2, pp. 1259-1263, November 2002. The method allocates one bit to the line and tone where the addition of said one bit requires the least increment in the total transmit power. To compute the energy increase required by the allocation of a bit, consider a given bit allocation {bk,l}. From equation (3), the SINR required to convey bk,l bits through the k-th tone of the l-th line is expressed byγ(bk,l)=Γ(2bk,l−2).  (4)
Let Hk represent the channel matrix associated with the k-tone, and [Hk]m,n its (m,n)-th element. Defining
                                          y            k                    =                                    [                                                                                          γ                      ⁡                                              (                                                  b                                                      k                            ,                            1                                                                          )                                                              ⁢                                          σ                                              1                        ,                        k                                            2                                                                                                  [                                              H                        2                                            ]                                                              1                      ,                      1                                        2                                                  ⁢                                                                  ⁢                …                ⁢                                                                  ⁢                                                                            γ                      ⁡                                              (                                                  b                                                      k                            ,                                                          N                              l                                                                                                      )                                                              ⁢                                          σ                                                                        N                          l                                                ,                        k                                            2                                                                                                  [                                              H                        k                                            ]                                                                                      N                        l                                            ,                                              N                        l                                                              2                                                              ]                        T                          ,                                  ⁢                                            [                              A                k                            ]                                      i              ,              j                                =                      {                                                                                                                                                                                                                  γ                              ⁡                                                              (                                                                  b                                                                      k                                    ,                                    i                                                                                                  )                                                                                      ⁡                                                          [                                                              H                                k                                                            ]                                                                                                            i                            ,                            j                                                    2                                                                                                      [                                                          H                              k                                                        ]                                                                                i                            ,                            i                                                    2                                                                    ,                                                                                                                          for                        ⁢                                                                                                  ⁢                        i                                            ≠                      j                                                                                                                                  0                      ,                                                                                                                          for                        ⁢                                                                                                  ⁢                        i                                            =                      j                                                                                  ,                                                          (        6        )            it was shown in the above-mentioned article that the power on the k-th tone of each line required to attain the target SINR expressed by equation (4) is given byεk=(I−Ak)−1yk,  (7)where εk=[εk,l . . . εk,Nl]T. Now, starting with this configuration, if one additional bit is allocated to a particular line in tone k, the power distribution among the lines will change to {circumflex over (ε)}k=[{circumflex over (ε)}k,l . . . {circumflex over (ε)}k,Nl]T. Lee's algorithm as mentioned above will allocate the additional bit in the line for which the total power increment, defined as the difference
                    ∑        j            ⁢                        ɛ          ^                          k          ,          j                      -                  ∑        j            ⁢              ɛ                  k          ,          j                      ,is minimized.
Another possible approach to the problem of bit allocation is to employ power allocation algorithms. After all, if the optimal power allocation is known, the number of bits can be determined using equation (1). The main difference is that, in power allocation, the fact that discrete bits will be transmitted is ignored, and it is assumed that the power in each line assumes continuous values. Thus, using power allocation algorithms along with equation (1) will produce a non-integer number of bits. This makes further processing necessary to come up with an integer solution, which may lower performance and increase complexity. Simple rounding is usually not suitable, since if the non-integer number of bits is rounded up to the closest integer number, a (power-)limitation may be violated while if the non-integer number of bits is rounded down to the closest integer number a substantial performance decrease may occur.
The most traditional power allocation method is the well-known water-filling algorithm, e.g. further described in R. Cendrillon, “Multi-user signal and spectral coordination for digital subscriber lines,” Ph.D. dissertation, Katholieke Universiteit Leuven, 2004 and B. Lee, Binder MIMO Channels, Ph.D. thesis, Stanford University, Stanford, USA, November 2004. The water-filling algorithm assumes that the signals are jointly processed at both ends of the communication link and that the total power to be transmitted, i.e., the sum of the powers of all lines involved, is limited. To describe this algorithm, let Hk=UkΣkVkH be the singular-value decomposition (SVD) of the channel matrix of the k-th tone, Hk. Assume that a pre-coding matrix is used given by Vk, and that the received signal is multiplied by UkH. Now, the matrices Uk and Vk are unitary, so that the pre-processor does not change the total transmitted power, i.e. the sum of the powers of all lines involved, and the receiver does not change the noise statistics. Furthermore, they reduce the channel to a diagonal matrix Σk. In other words, there are now several independent Gaussian channels, and the optimal power allocation can be easily determined. In fact, if εk,l is the symbol energy associated with the k-th tone of the l-th line, then
            ɛ              k        ,        l              =                  [                  γ          -                      Γ            ⁢                                          σ                k                2                                                              (                                      Σ                    k                                    )                                                  (                                      l                    ,                    l                                    )                                2                                                    ]            +        ,where
      (          Σ      k        )        (          l      ,      l        )    2is where is the square of the l-th diagonal element of Σk, σk2 is the noise variance at the k-th tone, [x]+=x if x>0, [x]+=0 otherwise, and λ is chosen so that the total power is equal to the maximum allowed.
One critical point of the water-filling solution is that it does not take into account any constraint on the power transmitted through each line. Indeed, although the use of a unitary pre-processing matrix incurs no increase in the total transmitted power, depending on the characteristics of the channel, the pre-processing operation may result in a substantial increase of the transmitted power in one particular line. This may lead to a violation of physical constraints imposed by the modem, for example unbalanced use of line drivers or restrictions by legislation or operators. To cope with this case, Cendrillon proposed, in the thesis “Multi-user signal and spectral coordination for digital subscriber lines” a power allocation algorithm, called optimal power allocation (OPA), for DSL systems assuming that the power on each line is constrained.
Some definitions are needed for the description of OPA. Consider the pre-processing operationxk=Pk{tilde over (x)}k  (8)where {tilde over (x)}k=[{tilde over (x)}lk . . . {tilde over (x)}Nlk]T is a vector containing the information symbols to be transmitted on the k-th tone of each line, Pk is the pre-coding matrix for tone k and xk is a vector of pre-coded symbols to be transmitted, as shown in FIG. 1. The power of each symbol {tilde over (x)}kn is denoted by {tilde over (s)}kn and the power of the pre-coded symbols xkn is denoted by skn. For the equivalent channel Gk=HkPk, define gkl,l as the square of the equivalent channel gain between the transmitted symbol {tilde over (x)}kl and the received symbol ykl. Assuming that crosstalk has been eliminated through some signal processing, the number of bits that can be conveyed by the k-th tone of the l-th line is given by
                                          b            k            l                    ⁡                      (                                          s                ~                            k              l                        )                          =                              log            2                    ⁡                      (                          1              +                                                                    g                    k                                          l                      ,                      l                                                        ⁢                                                            s                      ~                                        k                    l                                                                                                              σ                      ~                                        k                    2                                    ⁢                  Γ                                                      )                                              (        9        )            where σk2 is the assumed background noise variance at tone k and Γ is the SNR gap.
The optimal power allocation problem can be then stated as
                                          s            ~                    k          l                =                  arg          ⁢                                          ⁢                                    max                                                                    s                    ~                                    k                  l                                ,                                  ∀                  k                                ,                l                                      ⁢                                          ∑                l                            ⁢                                                ∑                  k                                ⁢                                                      b                    k                    l                                    ⁡                                      (                                                                  s                        ~                                            k                      l                                        )                                                                                                          (        10        )            subject to
                                                                        ∑                k                            ⁢                              s                k                l                                      ≤                          P              max                                ,                      ∀            l                          ⁢                                  ⁢                                            s              k              l                        ≥            0                    ,                      ∀            l                    ,                      k            .                                              (        11        )            
Notice that, considering the elements of the pre-processing matrix [Pk]l,m and assuming that the information symbols {tilde over (x)}k of each user are uncorrelated, one can write the output power for each modem as
                              s          k          l                ⁢                              ∑            m                    ⁢                                                                                                          [                                          P                      k                                        ]                                                        l                    .                    m                                                                              2                        ⁢                                                            s                  ~                                k                m                            .                                                          (        5        )            
The values of skl denote the power of the signals xlk . . . xNk.
The solution of the above optimization problem can be found by using Lagrange multipliers. In the thesis “Multi-user signal and spectral coordination for digital subscriber lines”, Cendrillon proposes the following iterative algorithm, which computes
            ∀      l        ,    k    ,                            s          ~                k        l            =                        [                                    1                                                ∑                  m                                ⁢                                                      λ                    m                                    ⁢                                                                                                                                    [                                                      P                            k                                                    ]                                                                          l                          ,                          m                                                                                                            2                                                                        -                          Γ              ⁢                                                σ                  k                  2                                                  g                  k                  l                                                              ]                +                        ∀      l        ,    k    ,                  λ        l            =                        [                                    λ              l                        +                          μ              (                                                                    ∑                    k                                    ⁢                                                            ∑                      m                                        ⁢                                                                                                                                                                                [                                                              P                                k                                                            ]                                                                                      l                              ,                              m                                                                                                                                2                                            ⁢                                                                        s                          ~                                                k                        m                                                                                            -                P                            )                                ]                +            until they converge.
Since OPA computes a power allocation, it may indicate that a non-integer number of bits should be transmitted through some tone. To determine an integer number of bits, the non-integer number of bits determined by OPA may be rounded down to the nearest integer value. This solution is referred to here as rounded OPA (ROPA). Note that the number of bits must be rounded down. Otherwise, the power limitation would be violated.
Thus, the problem is to achieve a method and arrangements for allocating an integer number of bits for a pre-processed multi-line DSL system. Hence, an integer number of bits to each tone of each line should be allocated, while the power on each line is limited to a specific upper power limitation while taking into account BER and other requirements and the operations of the pre-processor.
The problem with the above-described solutions is that most of them do not apply to the above mentioned problem addressed by this invention. Campello's bit-loading algorithm in “Practical Bit Loading for DMT” applies to single-line systems, while Lee's algorithm described in “Multi-user discrete bit-loading for DMT-based DSL systems” applies to multi-user (i.e. multi-line) systems with no crosstalk-mitigating processing, i.e. no pre-processing is used. The existing power allocation algorithms, such as OPA, fail to take into account the discrete nature of the transmitted bits.